#ifndef _allocTmpl_h_
#define _allocTmpl_h_

// allocTmpl.h
//
// General purpose memory allocation. This combines reference 
// counting and optional copy-on-write semantics.

#include "lock.h"

#include <stdexcept>
#include <algorithm>

// Disable warnings about unreferenced local functions (clone())
#ifdef WIN32
#pragma warning(disable:4505)
#endif


// Some machines do not define this
// This will work for most machines
#ifdef NEEDS_UINTPTR_T
typedef int uintptr_t;
#endif

namespace simple{
    //
    // _Allocator
    //
    //
    // Memory allocator object. My first implementation used new and
    // delete inside Alloc(). I moved memory allocation inside
    // _Allocator so derived classes can use private memory heaps or
    // some other scheme. I avoided the allocator objects in the
    // standard template library because the default implementation
    // on some platforms add a layer to enhance performance (ex: SGI)
    // by caching small memory buffers. No error checking is performed
    // by this object.
    // 内存分配对象。Alloc()内部使用new和delete。我从_Allocator中移除了
    // 内存分配功能，这样继承的类可以使用私有的内存堆或者其它什么模式。
    // 没有使用STL中的分配对象，是因为一些平台中添加了一个层来提升性能。
    // 其实，它只是一个内存指针的包装器。
    //
    // _AllocatorBase is the abstract base class for any _Allocator
    // object. I have put as much functionality inside _AllocatorBase
    // so derived objects can just add the necessary memory allocation
    // and deallocation.
    // _AllocatorBase是每个_Allocator的抽象基类。我已经写了很多功能，
    // 这样继承的对象可以只添加必要的内存分配和释放功能。
    //
    // An optional alignment value can be specified. This must be a
    // power of two and causes alignment at the specified byte
    // boundary. If alignment is specified, memory is allocated as a
    // (char*) pointer and converted to the appropriate type after
    // alignment. This will not cause problems on compilers that
    // enforce their own memory alignment (like MSVC) since we only
    // make sure the alignment is what we specified. In other words, if
    // MSVC is doing quad-word alignment and you specify double-word
    // alignment, _Allocator won't mess with the alignment at all!
    //
    //   0,1 = byte alignment (ie. no special processing)
    //   2   = word alignment
    //   4   = double-word alignment
    //   8   = quad-word alignment
    //
    // I left most methods public because _Allocator can potentially
    // be used by other classes.  The trailing underscore denotes that
    // this object is mainly for internal use.
    //
    // Replacements for _Allocator must handle allocation of 0 objects.
    // This is easily handled by allocating a single element (to make
    // any pointers returned valid).

    template<class T> class _AllocatorBase
    {
    public:
        _AllocatorBase (unsigned int n, unsigned int align)
            : _pRaw (0), _pData (0), _ref (0), _size (n), _align (align) {}
        // Derived classes will allocate memory but we store the relevant
        // details in the base class.

        virtual ~_AllocatorBase () {}
        // Derived classes will deallocate memory.

        bool lock   () const { return _lock.lock ();}
        bool unlock () const { return _lock.unlock ();}
        // Allow clients access to our lock

        operator       T* ()       { return _pData;}
        operator const T* () const { return _pData;}
        // Conversion to pointer of allocated memory type

        unsigned int size  () const { return _size;}  // Number of elements
        unsigned int ref   () const { return _ref;}   // Number of references
        unsigned int align () const { return _align;} // Alignment

        void addRef () { lock(); _ref++; unlock();}
        void subRef () 
        { 
            lock(); --_ref; unlock(); 
            if (_ref == 0) delete this;
        }
        // Increment or decrement the reference count.

    protected:
        virtual void allocate   () = 0;
        virtual void deallocate () = 0;
        // Pure virtual functions that derived classes provide to 
        // allocate/deallocate memory.

        T* alignPointer (void* raw)
        {
            T* p = reinterpret_cast<T*>(
                (reinterpret_cast<uintptr_t>(raw) + _align - 1) 
                & ~(_align - 1));
            // 对齐方法解释：
            // reinterpret_cast<uintptr_t>(raw)是将指针强制转化成uintptr_t
            // (一种足够大从而可以保存指针的类型)。uintptr_t同int型相同大小
            // & ~(_align - 1)中，~是取反的意思。&是与。
            // 例如当_align是4(4字节对齐)的时候，& ~(_align - 1)就是& ~3。
            // 也就是3的二进制是0000 0011，取反就是1111 1100。然后跟前面的
            // 结果取与，也就是前面的几位保持不变，之后的清0。这样就实现了对齐。
            // align = 0,1结果是不对齐；align = 2，换算(减一取反)后就是1110，
            // align = 4，换算得1100。8的话是1000。
            return p;
        }
        // Align the specified pointer to match our alignment and make it
        // a T* pointer. We cast to a uintptr_t to perform the
        // alignment and then we cast it to T*.

        _AllocatorBase            (const _AllocatorBase& src);
        _AllocatorBase& operator= (const _AllocatorBase& src);
        // No copy or assignment is allowed.


        char*        _pRaw;  // Raw allocated pointer
        T*           _pData; // Aligned pointer to our memory
        unsigned int _size;  // Number of elements allocated
        unsigned int _ref;   // Reference count
        unsigned int _align; // Memory alignment (modulus)

        mutable Lock _lock;  // Syncronization lock for accessing memory
        // This keyword can only be applied to non-static
        // and non-const data members of a class.
        // If a data member is declared mutable,
        // then it is legal to assign a value to
        // this data member from a const member function. 
    };



    template<class T> class _Allocator : public _AllocatorBase<T>
    {
    public:
        explicit _Allocator (unsigned int n, unsigned int align = 0) 
        : _AllocatorBase<T> (n, align)
        {
            allocate ();
            addRef ();
        }

        virtual ~_Allocator () { deallocate();}

    private:
        virtual void allocate () 
        {
            if (_size == 0) {
                // Eliminate possibility of null pointers by allocating 1 item.
                _pData = new T [1];
                _pRaw  = 0;
                return;
            }

            if (_align < 2) {
                // Let the compiler worry about any alignment
                _pData = new T [_size];
                _pRaw  = 0;
            }
            else {
                // Allocate additional bytes to guarantee alignment.
                // Then align and cast to our desired data type.
                _pRaw  = new char [sizeof(T) * _size + (_align - 1)];
                _pData = alignPointer (_pRaw);
            }
        }
        // Allocate our memory for _size elements of type T with the
        // alignment specified by _align. 0 and 1 specify no alignment,
        // 2 = word alignment, 4 = double-word alignment, ... This must
        // be a power of 2.

        virtual void deallocate ()
        { 
            // Decide which pointer we delete
            if (_pRaw)
                delete [] _pRaw;
            else
                delete [] _pData;
            _pRaw  = 0;
            _pData = 0;
        }

        _Allocator            (const _Allocator& src);
        _Allocator& operator= (const _Allocator& src);
        // No copy or assignment is allowed.
    };

    //
    // Alloc
    //
    // Features of Alloc
    //   - General purpose heap-based memory allocation.
    //   - Reference counting to share underlying memory.
    //   - Offers simple array, [], semantics with exception support.
    //     stl exceptions are used.
    //   - For performance, no time is spent initializing memory.
    //   - Custom memory allocation can replace the default heap
    //     based allocation (_Allocator).

    template<class T, class A = _Allocator<T> > 
    class Alloc
    {
    public:
        static Alloc& gNull ();
        // We return this object for any null allocations
        // It actually allocates 1 byte to make all the member
        // functions valid.

        Alloc  ();
        // Null allocation. Returns pointer to gNull() memory

        explicit Alloc  (unsigned int size, unsigned int align=0);
        ~Alloc ();
        // Allocate the specified bytes, with the correct alignment.
        // 0 and 1 specify no alignment. 2 = word alignment, 
        // 4 = double-word alignment. Must be a power of 2.

        Alloc            (const Alloc& src);
        Alloc& operator= (const Alloc& src);
        // We need our own copy constructor and assignment operator.

        unsigned int  size   () const { return _pMem->size ();}
        unsigned int  ref    () const { return _pMem->ref ();}
        bool          isNull () const { return (_pMem == gNull()._pMem);}

        bool lockStorage   () const { return _pMem->lock ();}
        bool unlockStorage () const { return _pMem->unlock ();}
        // Allow clients access to our lock

        const T* data () const { return *_pMem;}
        T*       data ()       { return *_pMem;}
        // Access to the beginning of our memory region. Use sparingly

        const T& operator[] (unsigned int index) const;
        T&       operator[] (unsigned int index);
        // Access a specific element. Throws the STL range_error if
        // index is invalid.

        virtual A* clone ();
        // Duplicate the memory in the underlying Allocator.
        // Derived classes can override this to perform their own 
        // clone, if shallow copying is not sufficient. It T
        // specifies an object that cannot be blindly copied, you will
        // need to override this function.

        void duplicate ();
        // Breaks any reference counting and forces this object to 
        // have its own copy.

    protected:
        A*   _pMem;             // Pointer to our allocated memory

        static Alloc* _sNull; // Our null object
    };

    template<class T, class A>
    void            Alloc<T, A>::duplicate ()
    {
        if (ref() == 1) {
            return;  // No need to duplicate
        }

        // Duplicate our existing memory
        A* copy = clone ();

        _pMem->subRef ();  // Remove reference from existing object
        _pMem = copy;      // Replace it with our duplicated data
    }

    template<class T, class A>
    Alloc<T,A>* Alloc<T, A>::_sNull = 0;

    template<class T, class A>
    Alloc<T,A>& Alloc<T, A>::gNull ()
    {
        if (!_sNull)
            _sNull = new Alloc (0);
        return *_sNull;
    }

    // 构造函数和析构函数
    template<class T, class A>
    Alloc<T, A>::Alloc () : _pMem (0)
    {
        // Point ourself to sNull. We can't do an assignment in the
        // constructor since it will try to deallocate something
        // that doesn't exist.
        _pMem = gNull()._pMem;
        _pMem->addRef ();
    }

    template<class T, class A>
    Alloc<T, A>::Alloc (unsigned int size, unsigned int align) : _pMem (0)
    {
        _pMem = new A(size, align);
    }

    template<class T, class A>
    Alloc<T, A>::~Alloc ()
    {
        _pMem->subRef ();
    }

    template<class T, class A>
    Alloc<T, A>::Alloc (const Alloc& src)
    {
        src.lockStorage ();
        _pMem = src._pMem;
        _pMem->addRef ();
        src.unlockStorage ();
    }

    // 成员
    template<class T, class A>
    Alloc<T, A>&    Alloc<T, A>::operator= (const Alloc& src)
    {
        // Make sure we don't copy ourself!
        if (_pMem == src._pMem)
        return *this;

        // Remove reference from existing object. addRef() and subRef()
        // do not throw so we don't have to worry about catching an error
        _pMem->subRef ();
        src.lockStorage ();
        _pMem = src._pMem;
        _pMem->addRef ();  // Add reference to our new object
        src.unlockStorage ();

        return *this;
    }


    template<class T, class A>
    const T&        Alloc<T, A>::operator[] (unsigned int index) const
    {
        if (index >= size())
        // Throw a standard STL exception
        throw std::range_error ("Index out of range");

        return *(data() + index);
    }

    template<class T, class A> 
    T&              Alloc<T, A>::operator[] (unsigned int index)
    {
        if (index >= size())
            // Throw a standard STL exception
            throw std::range_error ("Index out of range");

        return *(data() + index);
    }


    template<class T, class A>
    A*              Alloc<T, A>::clone ()
    {
        lockStorage ();

        A* copy = new A (_pMem->size(), _pMem->align());

        // Shallow copy
        T* src = *_pMem;
        T* dst = *copy;
        std::copy (src, &(src[_pMem->size()]), dst);

        unlockStorage ();
        return copy;
    }
}

#endif // _allocTmpl_h_
